#include "LinkTree.h"

LTNode *CreateTreeNode(ElementType element)
{
    LTNode *newNode = (LTNode*)malloc(sizeof(LTNode));
    if (newNode == NULL)
    {
        printf("树节点申请空间失败！\n");
        return NULL;
    }
    newNode->data = element;
    newNode->firstChild = NULL;
    newNode->nextSbling = NULL;
    newNode->parent = NULL;
    return newNode;
}

bool ConnectBranch(LTNode *parent, LTNode *child)
{
    if (parent == NULL || child == NULL)
    {
        printf("要连接的节点为空！\n");
        return false;
    }
    // 头插，无序树，有序树可用尾插
    child->nextSbling = parent->firstChild;
    parent->firstChild = child;
    child->parent = parent;
    return false;
}

void InitTree(LTree *tree)
{
    tree->root = CreateTreeNode(0);
}

void TravelNode(LTNode *node, int deepth, void (*funcPtr)(ElementType))
{
    if (node == NULL || funcPtr == NULL)
    {
        return;
    }
    if (node->parent != NULL){
        for (int i = 0; i < deepth; i++)
        {
            printf("  ");
        }
        //printf("%s\n", node->data);
        funcPtr(node->data);
    }
    // 深度优先遍历：子结点优先
    TravelNode(node->firstChild, deepth+1, funcPtr);
    TravelNode(node->nextSbling, deepth, funcPtr);

    // 广度优先遍历：层次遍历
    // TravelNode(node->nextSbling, deepth);
    // TravelNode(node->firstChild, deepth+1);
}

void TravelTree(LTree *tree, void (*funcPtr)(ElementType))
{
    TravelNode(tree->root, -1, funcPtr);
}

bool DisconnectBranch(LTNode *parent, LTNode *child)
{
    if (parent == NULL || child == NULL)
    {
        return false;
    }
    LTNode *travelPoint = parent->firstChild;
    if (travelPoint == NULL)
    {
        return false;
    }
    else if (travelPoint == child)
    {
        parent->firstChild = travelPoint->nextSbling;
        child->nextSbling = NULL;
        child->parent = NULL;
        return true;
    }
    else 
    {
        while (travelPoint->nextSbling != NULL)
        {
            if (travelPoint->nextSbling == child)
            {
                travelPoint->nextSbling = child->nextSbling;
                child->nextSbling = NULL;
                child->parent = NULL;
                return true;
            }
            travelPoint = travelPoint->nextSbling;
        }
    }
    
    return false;
}

void FreeTreeNode(LTNode *node, void (*funcPtr)(ElementType)) 
{
    if (node == NULL)
    {
        return;
    }
    LTNode *TravelNode = node->firstChild;
    while (TravelNode != NULL)
    {
        LTNode *nextNode = TravelNode->nextSbling;
        FreeTreeNode(TravelNode, funcPtr);
        TravelNode = nextNode;
    }
    if (funcPtr != NULL && node->parent != NULL)
    {
        funcPtr(node->data);
    }
    
    free(node);
}
void FreeTree(LTree *tree, void (*funcPtr)(ElementType))
{
    FreeTreeNode(tree->root, funcPtr);
    tree->root = NULL;
}

int GetTreeNodeHeight(LTNode *node) 
{
    if (node == NULL)
    {
        return 0;
    }
    int height = 0;
    LTNode *TravelNode = node->firstChild;
    while (TravelNode != NULL)
    {
        // 递归计算孩子的高度
        int childHeight = GetTreeNodeHeight(TravelNode); 
        height = height > childHeight ? height : childHeight;
        TravelNode = TravelNode->nextSbling;
    }
    return height + 1;
}
int GetTreeHeight(LTree *tree)
{
    return GetTreeNodeHeight(tree->root);
}

LTNode* FindNode(LTNode *node, ElementType element, bool (*funcPtr)(ElementType, ElementType))
{
    if (node == NULL)
        return NULL;
    if (funcPtr != NULL && node->parent != NULL && funcPtr(element, node->data) == true)
        return node;
    LTNode* targetNode = FindNode(node->firstChild, element, funcPtr);
    if (targetNode != NULL)
        return targetNode;
    targetNode = FindNode(node->nextSbling, element, funcPtr);
    if (targetNode != NULL)
        return targetNode;
}

LTNode *FindTreeNode(LTree *tree, ElementType element, bool (*funcPtr)(ElementType, ElementType))
{

    return FindNode(tree->root, element, funcPtr);
}
